#include <iostream>
#include <stdlib.h>
#include <time.h>
#include "graph.h"

arc::arc()
{
    adjvex = -1;
    nextArc = NULL;
}


vex::vex()
{
    vote = 0;
    voteAbility = 1;
    isSelect = 0;
    isInfected = 0;
    //isInfectedBefore = -1;
    isImmune = 0;
    degree = 0;
    nextArc = NULL;
}

int vex::addArc(int v)
{
    arc* tmp = nextArc;
    if(tmp == NULL)
    {
        nextArc = new arc;
        nextArc->adjvex = v;
        degree ++;
        return 1;
    }

    while(tmp->nextArc != NULL)
    {
        if(tmp->adjvex == v)
        {
            return 1;
        }
        tmp = tmp->nextArc;
    }

    if(tmp->adjvex == v)
        return 1;

    tmp->nextArc = new arc;
    tmp->nextArc->adjvex = v;
    degree ++;
    return 1;
}


graph::graph()
{
    vexChart = NULL;
    vexNum = 0;
    f = -1;
    selectNum = 0;
    infectRate = 0;
    coreNum = 0;
}

int graph::clearVote()
{
    for(int t = 0; t < vexNum; t ++)
        (vexChart+t)->vote = 0;
    return 1;
}


int graph::getF()
{
    long count = 0;
    for(int t = 0; t < vexNum; t ++)
        count += (vexChart+t)->degree;
    f = 1.0/count;
    return 1;
}


int graph::updateVA(int v)
{
    /*
    vex* tmpVex;
    for(int t = 0; t < vexNum; t ++)
    {
        tmpVex = vexChart+t;
        if(tmpVex->isSelect == 1)
        {
            tmpVex->voteAbility = 0;
            continue;
        }
        if(tmpVex->voteAbility - f > 0)
            tmpVex->voteAbility = tmpVex->voteAbility;
        else
            tmpVex->voteAbility = 0;
    }
    */

    arc* tmpArc;
    tmpArc = (vexChart + v)->nextArc;
    while(tmpArc != NULL)
    {
        if(vexChart[tmpArc->adjvex].isSelect == 1)
        {

            tmpArc = tmpArc->nextArc;
            continue;
        }

        if(vexChart[tmpArc->adjvex].voteAbility-f > 0)
            vexChart[tmpArc->adjvex].voteAbility = vexChart[tmpArc->adjvex].voteAbility-f;
        else
            vexChart[tmpArc->adjvex].voteAbility = 0;

        tmpArc = tmpArc->nextArc;
    }
    return 1;
}

int graph::initVex()
{
    vex* tmp;
    for(int t = 0; t < vexNum; t ++)
    {
        tmp = vexChart+t;
        tmp->vote = 0;
        tmp->voteAbility = 1;
        tmp->isSelect = 0;
        tmp->isInfected = 0;
        tmp->isSpread = 0;
        tmp->isImmune = 0;
        //tmp->isInfectedBefore = -1;
    }
    selectNum = 0;
    return 1;
}

int graph::addArc(int v1, int v2)
{
    if(v1 == v2)
        return 1;
    vexChart[v1].addArc(v2);
    vexChart[v2].addArc(v1);
    return 1;
}

int graph::setVex(int vn)
{
    vexNum = vn;
    if(vexChart!= NULL)
        delete [] vexChart;
    vexChart = new vex[vexNum];
    return 1;
}


int graph::setInfectRate(double i)
{
    infectRate = i;
    return 1;
}

int graph::setCoreNum(int n)
{
    coreNum = n;
    return 1;
}


int graph::selectByDegree()
{
    initVex();
    int state;
    vex* tmp, *maxVex;
    int max;
    while(selectNum < coreNum)
    {
        state = 0;
        for(int t = 0; t < vexNum; t ++)
        {
            tmp = vexChart+t;
            if(tmp->isSelect == 1)
                continue;
            if(state == 0)
            {
                max = tmp->degree;
                maxVex = tmp;
                state = 1;
            }
            else
            {
                if(tmp->degree > max)
                {
                    max = tmp->degree;
                    maxVex = tmp;
                }
            }
        }//for
        maxVex->isSelect = 1;
        selectNum ++;
    }

    return 1;

}


int graph::selectByVote()
{
    //selectNum = 0;
    initVex();
    double maxVote;
    vex *tmp, * maxVex;
    int state, maxVexPosi;

    while(selectNum < coreNum)
    {
        clearVote();
        vote();
        //updateVA();
        state = 0;

        for(int t = 0; t < vexNum; t ++)
        {
            tmp = vexChart+t;
            if(tmp->isSelect == 1)
                continue;
            if(state == 0)
            {
                maxVote = tmp->vote;
                maxVex = tmp;
                maxVexPosi = t;
                state = 1;
            }
            else
            {
                if(tmp->vote > maxVote)
                {
                    maxVote = tmp->vote;
                    maxVex = tmp;
                    maxVexPosi = t;
                }
            }
        }//for

        maxVex->isSelect = 1;
        maxVex->voteAbility = 0;
        selectNum ++;
        updateVA(maxVexPosi);
    }
    return 1;
}


int graph::vote()
{
    //std::srand(std::time(NULL));
    arc *tmpArc;
    vex* tmpVex;
    for(int t = 0; t < vexNum; t ++)
    {
        tmpVex = vexChart+t;
        if(tmpVex->isSelect == 1)
            continue;
        tmpArc = tmpVex->nextArc;
        while(tmpArc != NULL)
        {
            if(vexChart[tmpArc->adjvex].isSelect == 1)
            {
                tmpArc = tmpArc->nextArc;
                continue;
            }
            tmpVex->vote += vexChart[tmpArc->adjvex].voteAbility;
            tmpArc = tmpArc->nextArc;
        }//while
    }
    return 1;

}


int graph::infect()
{
    std::srand(time(NULL));

    for(int t = 0; t < vexNum; t ++)
    {
        if(vexChart[t].isSelect == 1)
        {
            vexChart[t].isInfected = 1;
            vexChart[t].isSpread = 0;
        }
    }

    int isFinish = 0;
    vex *tmpVex;
    arc *tmpArc;
    while(isFinish == 0)
    {
        isFinish = 1;
        for(int t = 0; t < vexNum; t ++)
        {
            if(vexChart[t].isInfected == 0 || vexChart[t].isSpread == 1)
            {
                continue;
            }
            tmpVex = vexChart+t;
            tmpVex->isSpread = 1;
            tmpArc = tmpVex->nextArc;
            while(tmpArc != NULL)
            {
                if(vexChart[tmpArc->adjvex].isInfected == 0 &&
                        vexChart[tmpArc->adjvex].isImmune == 0)
                {
                    if(std::rand()%100 <= infectRate*100)
                    {
                        vexChart[tmpArc->adjvex].isInfected = 1;
                        vexChart[tmpArc->adjvex].isSpread = 0;
                    }
                    isFinish = 0;
                    vexChart[tmpArc->adjvex].isImmune = 1;
                }
                tmpArc = tmpArc->nextArc;
            }//while

        }//for
    }//while
    return 1;
}


double graph::infectSize()
{
    double count = 0;
    for(int t = 0; t < vexNum; t ++)
    {
        if(vexChart[t].isInfected == 1)
            count ++;
    }
    return count / vexNum;
}



int graph::printVex()
{
    vex* tmpVex;
    arc* tmpArc;

    for(int t = 0; t < vexNum; t ++)
    {
        tmpVex = vexChart+t;
        std::cout << t << ":";
        tmpArc = tmpVex->nextArc;
        while(tmpArc != NULL)
        {
            std::cout << " " << tmpArc->adjvex;
            tmpArc = tmpArc->nextArc;
        }
        std::cout << std::endl;
    }
    return 1;
}
